/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};
*/

class Solution
{
public:
    Node *flatten(Node *head)
    {
        flattenAndReturnTail(head);
        return head;
    }

    Node *flattenAndReturnTail(Node *head)
    {
        if (head == nullptr)
        {
            return nullptr;
        }
        Node *cur = head;
        while (cur->next != nullptr)
        {
            Node *next = cur->next;
            if (cur->child != nullptr)
            {
                // recursive flatten childs
                Node *subHead = cur->child;
                Node *subTail = flattenAndReturnTail(cur->child);
                cur->child = nullptr;
                // concat
                cur->next = subHead;
                subHead->prev = cur;
                next->prev = subTail;
                subTail->next = next;
            }
            cur = next;
        }
        if (cur->child != nullptr)
        {
            Node *subTail = flattenAndReturnTail(cur->child);
            cur->next = cur->child;
            cur->child->prev = cur;
            cur->child = nullptr;
            return subTail;
        }
        else
        {
            return cur;
        }
    }
};